#include<iostream>
#include<vector>
using namespace std;

int findMin(vector<int>& nums){
    int left = 0, right = nums.size() - 1;

    //利用二段性,以最后一个元素为区分值
    //最小值左边元素都大于最后一个元素，最小值右边都小于等于最后一个元素
    //直接找最小值
    while(left<right){
        int mid = left + (right - left) / 2;

        if(nums[mid]>nums[nums.size()-1]){
            left = mid + 1;
        }
        else{
            right = mid;
        }
    }

    //以第一个元素为区分值
    //最小值元素左边都大于等于第一个元素，最小值右边都小于第一个元素
    //找最大值，最小值就是最大值后一个
    while(left<right){
        int mid = left + (right - left + 1) / 2;

        if(nums[mid]>=nums[0]){
            left = mid;
        }
        else{
            right = mid - 1;
        }
    }
    if(left!=nums.size()-1){
        left++;
    }
    return nums[left];
}

//0到n-1缺失的数字
//0 1 2 3 4 6 7
//0 1 2 3 4 5 6
int takeAttendance(vector<int>& nums){
    int left = 0, right = nums.size() - 1;

    while(left<right){
        int mid = left + (right - left) / 2;

        if(nums[mid]==mid){
            left = mid + 1;
        }
        else{
            right = mid;
        }
    }

    if(left==nums.size()&&nums[left]==left){
        left++;
    }

    return left;
}

int main(){
    vector<int> nums = {};

    int min = findMin(nums);
    cout << min;
    return 0;
}